# 假设有不限量的100、50、20、5、1的纸币，给你376块钱，如何找钱是找的纸币数量最少？

def open_money(t,n):
	m = [0 for _ in t]
	for index, money in enumerate(t):
		y = n // money
		m[index] = y
		n = n % money
	return m,n

t = [100,50,20,5,1]  # 钱币
# print(open_money(t,376))


# 小偷去商店偷东西，商品重wkg，价值v元，小偷背包只能装ykg东西，问如何偷的价值最高？
# 分数背包（可以取部分）
def frantional_backpack(goods, w):
	m = [0 for _ in range(len(goods))]
	total = 0
	for i,(price,weight) in enumerate(goods):
		if w >= weight:
			m[i] = 1
			w -= weight
			total += price
		else:
			m[i] = w / weight
			w = 0
			total += m[i] * price
			break
	return total,m


goods = [(60,10),(100,20),(120,30)]  # 每个商品(价格，重量)
# goods.sort(key=lambda x: x[0]/x[1], reverse=True)  # 根据价值排序
# print(frantional_backpack(goods,50))


# 拼接最大的数
# 例如：32，94，128，1286，6，71 =》94716321286128  注意1286，128  765 7652
li = ['32', '94', '128', '1286', '6', '71']
n = len(li)
for i in range(n-1):
	for j in range(n-1-i):
		if li[j] + li[j+1] < li[j+1] + li[j]:
			li[j],li[j+1] = li[j+1],li[j]
print(li)



# 活动选择问题
# 假设有n个活动，每个活动要占用场地，活动开始时间s和结束时间f 【s,f）
# 问规定时间内如何安排使举行活动最多（活动得在规定时间结束）



